package 中等.滑动窗口;

import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 给你一个整数数组 nums 和两个正整数 m 和 k 。
 * 请你返回 nums 中长度为 k 的 几乎唯一 子数组的 最大和 ，如果不存在几乎唯一子数组，请你返回 0 。
 * 如果 nums 的一个子数组有至少 m 个互不相同的元素，我们称它是 几乎唯一 子数组。
 * 子数组指的是一个数组中一段连续 非空 的元素序列。
 *
 * @ https://leetcode.cn/problems/maximum-sum-of-almost-unique-subarray/description/
 * @date 2024/07/22
 */
public class 几乎唯一子数组的最大和_2841 {

    public static void main(String[] args) {

    }

    /**
     * 滑动窗口
     * 窗口的长度固定 k，用哈希表记录元素出现的次数
     */
    public long maxSum(List<Integer> nums, int m, int k) {
        long ans = 0;

        Map<Integer, Integer> map = new HashMap<>();
        long sum = 0;
        int left = 0, right = 0;
        while (right < nums.size()) {

            sum += nums.get(right);
            map.put(nums.get(right), map.getOrDefault(nums.get(right), 0) + 1);
            right++;
            if (right - left < k) {
                continue;
            }

            if (map.size() >= m) {
                ans = Math.max(ans, sum);
            }

            sum -= nums.get(left);
            map.put(nums.get(left), map.get(nums.get(left)) - 1);
            if (map.get(nums.get(left)) == 0) {
                map.remove(nums.get(left));
            }
            left++;
        }
        return ans;
    }

}
